package oj_leetcode;

import java.util.*;

public class SubstringWithConcatenationOfAllWords {

    public List<Integer> findSubstring(String s, String[] words) {
        int sLen = s.length();
        int wordCount = words.length;
        int wordLength = words[0].length();
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        // 存hash表提高查询效率
        for (int i = 0; i < words.length; i++) {
            if (map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            } else {
                map.put(words[i], 1);
            }
        }
        TreeMap<Integer, String> indexStr = new TreeMap<>();
        // 遍历s，寻找words出现的下标List
        for (int i = 0; i <= sLen - wordLength; i++) {
            String curr = s.substring(i, i + wordLength);
            if (map.containsKey(curr)) {
                indexStr.put(i, curr);
            }
        }
        // 遍历indexStr，找到符合条件的连续index
        indexStr.forEach((k, v) -> {
            int kI = k;
            Map<String, Integer> forPair = new HashMap<>(map);
            int count = 0;
            while (count < wordCount && indexStr.containsKey(k)) {
                v = indexStr.get(k);
                k = k + wordLength;
                count++;
                if (forPair.containsKey(v)) {
                    if (forPair.get(v) == 1) {
                        forPair.remove(v);
                    } else {
                        forPair.put(v, forPair.get(v) - 1);
                    }
                } else {
                    break;
                }
            }
            if (forPair.isEmpty()) {
                res.add(kI);
            }
        });

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new SubstringWithConcatenationOfAllWords().findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}));
    }

}
